package com.example.demo.arithmetic.algorithm.sort;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @Description: 选择排序
 * @Author: LLL
 * @Date: 2020-03-16 22:07
 **/
public class SelectSort {
    public static void main(String[] args) {
        int arr[] = new int[80000];
        IntStream.range(0, 80000).forEach(item -> {
            arr[item] = (int) (Math.random() * 8000000 + 1);
        });
        long start = System.currentTimeMillis();
        selectSort2(arr);
        System.out.println("耗时" + String.valueOf(System.currentTimeMillis() - start) + "ms");
        System.out.println(Arrays.toString(arr));
    }

    /**
     * Description: 选择排序
     * 1.数组一共进行数组长度-1轮排序
     * 2.找到最小值，如果小于第一个位置的元素那么跟第一个交换位置，
     * 否则进行下一轮，从剩下的再找最小值放前面
     * 101 34 119 1
     *
     * @param arr
     * @return: void
     * @author: liull
     * @date: 2020/3/16 22:13
     */
    private static void selectSort(int[] arr) {
        for (int j = 0; j < arr.length - 1; j++) {
            // 假定最小索引处为最小值
            int minIndex = j;
            int min = arr[minIndex]; // 4
            for (int i = j + 1; i < arr.length; i++) {
                if (min > arr[i]) {
                    min = arr[i];
                    minIndex = i;
                }
            }
            // 最小值放在arr[0] 交换了
            arr[minIndex] = arr[j];
            arr[j] = min;
        }

        // 第二轮找第二小的值
       /* minIndex = 1;
        min = arr[1]; // 4
        for (int i = 1 + 1; i < arr.length; i++) {
            if (min > arr[i]) {
                min = arr[i];
                minIndex = i;
            }
        }
        // 最小值放在arr[0] 交换了
        arr[minIndex] = arr[1];
        arr[1] = min;*/
    }


    /**
     * 选择排序方法2
     *
     * @param arr
     */
    private static void selectSort2(int[] arr) {
        // 外层控制循环次数

        for (int right = arr.length - 1; right > 0; right--) {
            // 假设最后一个元素最大，如果不是更新max值为最大的元素的索引
            int max = right;
            for (int i = 0; i < right - 1; i++) {
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            //            arr[max] 交换
            if (max != right) {
                swap(arr, max, right);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
